|
In functional programming, fold – also known variously as reduce, accumulate, aggregate, compress, or inject – refers to a family of higher-order functions that analyze a recursive data structure and through use of a given combining operation, recombine the results of recursively processing its constituent parts, building up a return value. Typically, a fold is presented with a combining function, a top node of a data structure, and possibly some default values to be used under certain conditions. The fold then proceeds to combine elements of the data structure's hierarchy, using the function in a systematic way. Folds are in a sense dual to unfolds, which take a "seed" value and apply a function corecursively to decide how to progressively construct a corecursive data structure, whereas a fold recursively breaks that structure down, replacing it with the results of applying a combining function at each node on its terminal values and the recursive results (catamorphism as opposed to anamorphism of unfolds). ==Folds as structural transformations== Folds can be regarded as consistently replacing the structural components of a data structure with functions and values. Lists, for example, are built up in many languages from two primitives: any list is either an empty list, commonly called ''nil'' ( foldr, by composing the function to act on the elements with cons, as:map f = foldr ((:) . f) [] where the period (.) is an operator denoting function composition. This way of looking at things provides a simple route to designing fold-like functions on other algebraic data structures, like various sorts of trees. One writes a function which recursively replaces the constructors of the datatype with provided functions, and any constant values of the type with provided values. Such a function is generally referred to as a catamorphism. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fold (higher-order function)」の詳細全文を読む スポンサード リンク
|